package com.michael.leetcode;

import org.junit.Test;

import java.util.Arrays;

public class SmallestDifference_16_06 {


    /**
     * 面试题 16.06. 最小差
    给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
    *
    示例：
    输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
    输出：3，即数值对(11, 8)

    提示：
    1 <= a.length, b.length <= 100000
    -2147483648 <= a[i], b[i] <= 2147483647
    正确结果在区间 [0, 2147483647] 内
     */


    /**
     * 思路：
     * step 1 先排序
     * step 2 a[x]-b[y] > 0 说明 a[x] > b[y] 由因为 b是按照升序排列的 所以 a[x]-b[y] 一定大于 a[x]-b[y+1]
     * step 3 a[x]-b[y] < 0 说明 a[x] < b[y] 由因为 a是按照升序排列的 所以 a[x]-b[y] 一定小于 a[x+1]-b[y+1]
     * step 4 根据2 和3条件移动双指针
     */
    public int smallestDifference(int[] a, int[] b) {
        if (a.length == b.length && a.length == 1) {
            return Math.abs(a[0] - b[0]);
        }
        Arrays.sort(a);
        Arrays.sort(b);
        long res = Long.MAX_VALUE;

        int x = 0;
        int y = 0;

        while (x < a.length && y < b.length){
            if (a[x] == b[y]){
                return 0;
            }

            long diff = (long)a[x] - (long)b[y];
            res = Math.min(Math.abs(diff), res);
            if (diff > 0){
                y++;
            }else {
                x++;
            }
        }

        return (int)res;
    }




    @Test
    public void test(){
        int[] a = {1,2,11,15};
        int[] b = {4,12,19,23,127,235};
        int i = smallestDifference(a, b);

    }


}